package leetcode._08_dynic;

import org.junit.Test;

import java.math.BigInteger;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;

/**
 * @author pppppp
 * @date 2022/3/28 15:38
 * 给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。
 * 请你从 nums 中找出并返回总和为 target 的元素组合的个数。
 * 题目数据保证答案符合 32 位整数范围。
 * <p>
 * 示例 1：
 * 输入：nums = [1,2,3], target = 4
 * 输出：7
 * 解释：
 * 所有可能的组合为：
 * (1, 1, 1, 1)
 * (1, 1, 2)
 * (1, 2, 1)
 * (1, 3)
 * (2, 1, 1)
 * (2, 2)
 * (3, 1)
 * 请注意，顺序不同的序列被视作不同的组合。
 * <p>
 * 示例 2：
 * 输入：nums = [9], target = 3
 * 输出：0
 *  
 * 提示：
 * 1 <= nums.length <= 200
 * 1 <= nums[i] <= 1000
 * nums 中的所有元素 互不相同
 * 1 <= target <= 1000
 * 进阶：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？
 */
public class _377_组合总和_Ⅳ {


    @Test
    public void T_0() {
        int[][] nums = {
                {10,20,30,40,50,60,70,80,90,100,110,120,130,140,150,160,170,180,190,200,210,220,230,240,250,260,270,280,290,300,310,320,330,340,350,360,370,380,390,400,410,420,430,440,450,460,470,480,490,500,510,520,530,540,550,560,570,580,590,600,610,620,630,640,650,660,670,680,690,700,710,720,730,740,750,760,770,780,790,800,810,820,830,840,850,860,870,880,890,900,910,920,930,940,950,960,970,980,990,111},
                {1,50}, {1, 2, 3}, {9}};
        int[] targets = { 999,200, 4, 3};
        int[] anss = {-1,982, 7, 0};
        for (int i = 2; i < nums.length; i++) {
            // System.out.println(combinationSum4(nums[i], targets[i]) == anss[i]);
            System.out.println(combinationSum4_01(nums[i], targets[i]) == anss[i]);
            path.clear();
            ans = 0;
        }
    }

    /*0.1 dp  完全背包  有序  外层遍历和 内层遍历 coin*/
    public int combinationSum4_01(int[] nums, int target) {

        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int j = 0; j < nums.length; j++) {
                if(i >= nums[j]){
                    dp[i] += dp[i-nums[j]];
                }
            }
        }
        return dp[target];
    }


    /*0.传统的回溯法  + 全排  依然超时
    * */
    LinkedList<Integer> path = new LinkedList<>();
    Integer ans = 0;

    public int combinationSum4(int[] nums, int target) {
        Arrays.sort(nums);
        dfs(0, nums, 0, target);
        return ans;
    }

    private void dfs(int i, int[] nums, int sum, int target) {
        if (i == nums.length || sum >= target) {
            if (sum == target) {
                ans += (int) getNum(path);
            }
            return;
        }

        for (int j = i; j < nums.length; j++) {
            if (sum > target) {
                break;
            }
            sum += nums[j];
            path.add(nums[j]);
            dfs(j, nums, sum, target);
            path.removeLast();
            sum -= nums[j];
        }
    }

    /*计算组合数*/
    private long getNum(LinkedList<Integer> path) {
        int size = path.size();
        HashMap<Integer, Integer> map = new HashMap<>();
        for (Integer integer : path) {
            map.put(integer,map.getOrDefault(integer,0)+1);
        }
        BigInteger t1 = BigInteger.ONE,t2 = BigInteger.ONE;
        while (size >1){
            t1 = t1.multiply(BigInteger.valueOf(size));
            size--;
        }
        for (Integer integer : map.keySet()) {
            Integer val = map.get(integer);
            while (val > 1){
                t2 = t2.multiply(BigInteger.valueOf(val));
                val--;
            }
        }
        return Integer.valueOf(String.valueOf(t1.divide(t2)));
    }


}
